package com.sise.Backtracking;

import java.util.ArrayList;
import java.util.List;

/**
 *      78. 子集
 *      给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 *      解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 *      示例 1：
 *      输入：nums = [1,2,3]
 *      输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 *
 */
public class _78_subsets {

    static public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(0, nums, result, new ArrayList<>());
        return result;
    }

    // tempList.remove(tempList.size() - 1) 有两种情况，一种是已经遍历过了，一种是超出 for 循环范围
    static private void dfs(int begin, int[] nums, List<List<Integer>> result, ArrayList<Integer> tempList) {
        result.add(new ArrayList<>(tempList));
        System.out.println("当前列表 " + tempList + "  结果集： " + result);
        System.out.println();

        for (int j = begin; j < nums.length; j++) {
            tempList.add(nums[j]);
            System.out.println("遍历过程中 begin = " + begin + "  此时 j = " + j);
            dfs(j + 1, nums, result, tempList);
            System.out.println("当前删除时，begin = " + begin + " j = " + j + "。   删除的值为：" + tempList.remove(tempList.size() - 1) + "。  删除之后的 tempList " + tempList);
        }
    }

    /**
     * 获取当前位置的值，然后与前面的临时列表值进行遍历组合，运行过后就明白
     */
    public static void main(String[] args) {
        int[] r = {1, 2, 3};
        System.out.println(subsets(r));
    }

    static public List<List<Integer>> subsets2(int[] nums) {

        // 定义结果集，首先添加空列表
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        // 第一层遍历以 nums.length 为长度，目的是为了遍历所有的数字
        for (int i = 0; i < nums.length; i++) {

            // 第二层遍历以 result.size() 当前结果集的长度，每次遍历都从 j = 0 开始添加数值到 temp 列表
            int all = result.size();
            for (int j = 0; j < all; j++) {
                List<Integer> tempList = new ArrayList<>(result.get(j));
                System.out.println("当前的tempList： " + tempList);
                tempList.add(nums[i]);
                result.add(tempList);

                System.out.println("当前结果：" + result + "  j=" + j);
                System.out.println(" ");
            }
        }
        return result;
    }
}
